
public class MyLinkedList {

    public static class Node {
        Node next;//前一个结点
        Node prev;//后一个结点
        int val;//值
        //构造方法
        public Node(int val) {
            this.val = val;
        }
    }
    public static Node head=new Node(0);
    {
        head.prev=head;
        head.next=head;
    }

    //头插法
    public void addFirst(int data){
        addIndex(1,data);
    }
    //尾插法
    public void addLast(int data){
        addIndex(size(),data);
    }
    //任意位置插入,第一个数据节点为1号下标
    public void addIndex(int index,int data){
        if (head==null) {
            System.exit(0);
        }
        Node cur=head.next;
        while (cur!=head&&index!=1) {
           cur=cur.next;
            index--;
        }
        if (index != 1) {
            return;
        }
        Node node=new Node(data);
        Node curPrev=cur.prev;
        curPrev.next=node;
        node.prev=curPrev;
        node.next=cur;
        cur.prev=node;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        if(Find(key)!=null) {
            return true;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){

        Node cur=Find(key);
        Node curNext=cur.next;
        Node curPrev=cur.prev;
        curPrev.next=curNext;
        curNext.prev=curPrev;
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if (head==null) {
            return;
        }
        Node cur=head.next;
        while (cur!=head) {
            Node curNext=cur.next;
            Node curPrev=cur.prev;
            if (cur.val==key){
                curPrev.next=curNext;
                curNext.prev=curPrev;
            }
            cur=curNext;
        }

    }
    //得到单链表的长度
    public int size(){
        if (head==null) {
            System.exit(0);
        }
        Node cur=head.next;
        int count=1;
        while (cur!=head) {
            cur=cur.next;
            count++;
        }
        return count;
    }

    public void display(){
        Node cur=head.next;
        while (cur!=head) {
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //删除全部结点
    public void clear(){
        head=null;
    }
    //尾删
    public void deleteLast() {
         delete(size());
    }
    //头删
    public void deleteFront() {
        delete(1);
    }
    //指定删
    public void delete(int index) {
        if(head==null) {
            System.exit(0);
        }
        Node cur=head.next;
        while (cur!=head&&index!=1) {
            cur=cur.next;
            index--;
        }
        if (index != 1) {
            System.out.println("没有找到要删除的结点");
            return;
        }
        Node curPrev=cur.prev;
        Node curNext=cur.next;
        curPrev.next=curNext;
        curNext.prev=curPrev;
    }
    public Node Find(int val) {
        if (head==null) {
            return null;
        }
        Node cur=head.next;
        int i=1;

        while (cur!=head) {
            if (cur.val==val) {
                return cur;
            }
            i++;
            cur=cur.next;
        }
        return null;
    }
    public void revise(int val,int date) {
            Node n=Find(val);
        if (n!=null) {
            n.val=date;
        }
    }
}